package 剑指offer.demo3;
//https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?

/**
 * 方法一：定义三个结点进行交换，注意第二个结点的合法性（把错误扼杀在摇篮里不要多想）
 * 方法二：本质一样还是交换，交换的方法不同多看下注释还是很好理解的
 */
public class 反转链表 {
    public ListNode ReverseList_1(ListNode head) {
        //合法性判断注意head.next；否则这个方法会越界
        if (head == null || head.next == null){
            return head;
        }
        //定义三个结点进行转向操作
        ListNode node1 = head;
        ListNode node2 = node1.next;
        ListNode node3 = node2.next;
        //在node3没到头时，进行转换操作
        while (node3 != null){
            //把node2的链子串在node1上;然后三个一起向后移动一步
            node2.next = node1;
            node1 = node2;
            node2 = node3;
            node3 = node3.next;
        }
        //此时node3到头了，但是node2的链子还没转（也就是最后一个），再操作一下
        node2.next = node1;
        //全部转向成功了，把头节点重新定义一下
        head.next = null;//这部可以省略，jvm会处理，后续会更新jvm部分
        head = node2;
        return head;//可以直接node2
    }

    public ListNode ReverseList_2(ListNode head) {
        //合法性判断注意head.next；否则这个方法会越界
        if (head == null || head.next == null){
            return head;
        }
        ListNode newHead = null;
        while (head != null){
            //定义一个临时结点
            ListNode cur = head;
            //把头节点后移，方便下一次定义的临时结点是下一个元素
            head = head.next;
            //把定义的临时结点，（头节点变化前所在位置）链接到新头后面
            cur.next = newHead;
            //新头节点后移
            newHead = cur;
        }
        //循环完时新链表创建成功头在newHead那里
        return newHead;
    }
    //题目给定链表类
    public class ListNode {
        int val;
        ListNode next = null;
        ListNode(int val) {
            this.val = val;
        }
    }

}
